\begin{exercise}
 Show that $f_i$ is an involution without a fixed point.
 That is, $f(f(x)) = x$ and $f(x) \ne x$ for all $x \in \{0,1\}^d$.
\end{exercise}

\begin{proof}
According to definition, $f_i(x)$ is x with $i^{th}$ position flipped, so $f_i(x) \neq x$. And $f_i(f_i(x))$ is x with $i^{th}$
position flipped twice, which goes back to x, so $f_i(f_i(x)) = x$.Therefore, $f_i$ is an involution without a fixed point.\\
\end{proof}

Let $S \subseteq \{0,1\}^d$. We define  $f_i(S)$ as the set arising from applying
$f_i$ to every element of $S$. Formally,
\begin{align*}
f_i(S) := \{ f_i(x) \ | \ x \in S \} \ .
\end{align*}
Given a set $S \subseteq \{0,1\}^d$, we call an index $i \in [n]$ {\em active} for $S$
if $f_i(S) \ne S$. 
\begin{exercise}
Let $d=3$ and $S = \{000, 100\}$. Which of the indices $1,2,3$ are active?
\end{exercise}

\begin{proof}
Let least significant digit be the 1'st position.\\
\[f_1(S) = \{001,101\} \neq S\]
\[f_2(S) = \{010,110\} \neq S\]
\[f_3(S) = \{100,000\} = S\]
So 1 and 2 are active.
\end{proof}

\begin{exercise}
 Show that $f$ is an involution. That is, $f(f(S)) = S$. Furthermore, show that
 the only fixed points of $f$ are $\emptyset$ and $\{0,1\}^d$.
\end{exercise} 

\begin{proof}
\[\forall x \in S, f(f(x)) = x \Rightarrow f(f(S))=S\]
Let's suppose that f(S)=S when $S \neq \{0,1\}^d\:and\: S \neq \emptyset$.Thus, there must exist an element $x\in S$ and an element $y\in \{0,1\}^d\backslash S$.Define a step as changing one number's 1 bit, such as $00000 \rightarrow 00001$.Obviously, one figure can walk into any other one in at most n steps(n is the number of bits).The path from x to y is followed, and the distance of neighbours is one step, which means $t_{k+1}=f_{i_k}(t_k)$.
\[x=t_0 \rightarrow t_1 \rightarrow\ldots\rightarrow t_n \rightarrow t_{n+1}=y\]
Since f(S)=S, $t_{k+1}\in S \Rightarrow t_{k+1}=f_{i_k}(t_k)\in S$.By induction, we can know that $y\in S$ on the base of $x\in S$,which results in conflict with the claim $y\in \{0,1\}^d\backslash S$. Therefore, the only fixed points of f are $\emptyset$ and $\{0,1\}^d$.
\end{proof}

\begin{exercise}
   Let $\mathcal{S} = { \{0,1\}^d \choose k }$. This is a set of sets, and each set $S \in \mathcal{S}$
   consists of exactly $k$ strings from $\{0,1\}^d$. Prove the following statements: 
   \begin{enumerate}
   \item $f$ is a bijection from $\mathcal{S}$ to $\mathcal{S}$.
   \item For $1 \leq k \leq 2^d-1$, this bijection is an involution
   without fixed points.
   \item $|\mathcal{S}|$ is even for $1 \leq k \leq 2^d-1$.
   \end{enumerate}
\end{exercise}

\begin{proof}
1. $\forall S_1 \neq S_2 \in \mathcal{S}, \exists x_1\in S_1, x_1 \notin S_2 \Rightarrow f(x_1)\in f(S_1),f(x_1)\notin f(S_2) \Rightarrow f(S_1)\neq f(S_2)$.So f is an injective. And $|\mathcal{S}|=|\mathcal{S}|$, so f is a surjective. Thus, $f$ is a bijection from $\mathcal{S}$ to $\mathcal{S}$.
\end{proof}

\begin{proof}
2. According to Exercise 4.10, For $1 \leq k \leq 2^d-1$, which means $S \neq \emptyset \: and\: S \neq \{0,1\}^d$, $f(S) \neq S$.So f is an bijection without fixed point.
\end{proof}

\begin{proof}
3. Since $f(S)\neq S$and $f(f(S))=S$, we say every S can be "married" with f(S).Thus,$|\mathcal{S}|$ is even for $1 \leq k \leq 2^d-1$.
\end{proof}

